package com.cty.twentySixthDay;


import java.util.LinkedList;
import java.util.Queue;

/*
 * 给你一个二叉树的根节点 root，检查它是否轴对称。
 * */
public class Q_39 {
    // 递归
    public boolean isSymmetric(TreeNode root) {
        return isSymmetric(root.left, root.right);
    }

    // 递归 这就是主包的思路 就是牛逼 时间复杂度O(n) 空间复杂度O(height) 用到了栈 栈的长度其实是height - 1 省略后面的减一 height是树的高度
    public boolean isSymmetric(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left != null && right != null && isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left) && right.val == left.val) {
            return true;
        } else {
            return false;
        }
    }

    // 力扣官方题解 方法一:递归
    /*
    *
    * 时间复杂度O(n) 空间复杂度O(n)
    * */
    public boolean isSymmetric2(TreeNode root) {
        if (root == null) return true;
        return check(root.left,root.right);
    }

    public boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return q.val == p.val && check(p.left,q.right) && check(p.right,q.left);
    }

    // 力扣官方题解 方法二:迭代
    /*
    * 思路: 用一个队列 分别将第一个节点的左节点加入其中 第二个节点的右节点加入其中(两个节点是从队列中取出的)
    *   时间复杂度O(n) 空间复杂度O(n)
    * */
    public boolean isSymmetric3(TreeNode root) {
        // 让头节点入队两次
        return check2(root,root);
    }
    public boolean check2(TreeNode left,TreeNode right) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(left);
        queue.offer(right);
        while (!queue.isEmpty()) {
            left = queue.poll();
            right = queue.poll();
            if (left == null && right == null) {
                continue;
            }
            if ((left == null || right == null) || left.val != right.val) {
                return false;
            }

            queue.offer(left.left);
            queue.offer(right.right);

            queue.offer(left.right);
            queue.offer(right.left);
        }
        return true;
    }
}
